package data_structure.stack;

import java.util.*;

/**
 * @Author: lijun
 * @Date: 2018/10/29 16:21
 * 给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。
 * 你可以假设网格的四个边均被水包围。
 *
 * 输入:
 * 11110
 * 11010
 * 11000
 * 00000
 * 输出: 1
 *
 * 输入:
 * 11000
 * 11000
 * 00100
 * 00011
 * 输出: 3
 */
public class NumIslands {

    public int numIslands(char[][] grid) {
        int islandsNum = 0;
        if (grid.length == 0) {
            return 0;
        }
        Boolean[][] visited = new Boolean[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == '1') {
                    islandsNum++;
                    visited[i][j] = true;
                    dfs(i + ":" +j,visited,grid);
                }
            }
        }
        return islandsNum;
    }

    private void dfs(String node, Boolean[][] visited, char[][] grid) {
        Stack<String> stack = new Stack<>();
        stack.push(node);
        while (!stack.isEmpty()) {
            String cur = stack.peek();
            Set<String> neighbours = getNeighbours(cur,grid);
            if (neighbours.isEmpty()) {
                stack.pop();
            } else {
                for (String neighbor : getNeighbours(cur,grid)) {
                    int i = Integer.parseInt(neighbor.split(":")[0]);
                    int j = Integer.parseInt(neighbor.split(":")[1]);
                    if (grid[i][j] == '1') {
                        grid[i][j] = '0';
                        visited[i][j] = true;
                        stack.push(neighbor);
                    }
                }
            }
        }
    }

    private Set<String> getNeighbours(String cur, char[][] grid) {
        Set<String> neighbours = new HashSet<>();
        int i = Integer.parseInt(cur.split(":")[0]);
        int j = Integer.parseInt(cur.split(":")[1]);
        if (i > 0 && grid[i-1][j] == '1') {
            neighbours.add((i-1) + ":" + j);
        }
        if (i < grid.length-1 && grid[i+1][j] == '1') {
            neighbours.add((i+1) + ":" + j);
        }
        if (j > 0 && grid[i][j-1] == '1') {
            neighbours.add(i + ":" + (j-1));
        }
        if (j < grid[i].length-1 && grid[i][j+1] == '1') {
            neighbours.add(i + ":" + (j+1));
        }
        return neighbours;
    }


    public static void main(String[] args) {
//        char[][] grid = {{'1','1','1','1','0'},{'1','1','0','1','0'},{'1','1','0','0','0'},{'0','0','0','0','0'}};
        char[][] grid = {{'1','1','1'},{'0','1','0'},{'1','1','1'}};
        System.out.printf("" + new NumIslands().numIslands(grid));
    }
}
